система научных представлений о неоднократном развитии ледников, покрывавших огромные площади Земли. Идеи о большем, чем ныне, распространении древних ледников в горах высказывались исследователями Альп уже в конце 18 - начале 19 вв. Но зарождение Л. т. относится к 40-м гг. 19 в., когда с деятельностью древних ледников начали связывать происхождение рассеянных на обширных пространствах Европы и Северной Америки эрратических валунов (См. Эрратические валуны) - обломков горных пород, коренные местонахождения которых удалены на сотни и тысячи км от данной местности. Ледниковый генезис отложений, содержащих подобные валуны, обосновали для предгорий Альп швейцарские учёные И. Венец, Ж. де Шарпантье и Ж. Л. Агассис, для Северной Европы - немецкий геолог А. Бернгарди (1832), для Скандинавии (1840) и Северной Америки (1846) - Ж. Л. Агассис. Однако вплоть до середины 70-х гг. 19 в. большинство учёных считало, что отложения, включающие эрратические валуны, являются морскими осадками, среди которых сами валуны были рассеяны когда-то айсбергами. Эти взгляды, получившие название теории дрифта, полнее всего были развиты в 30-х гг. английским геологом Ч. Лайелем (См. Лайель). В развенчании теории дрифта и укреплении представлений о материковом оледенении велики заслуги русских учёных К. Ф. Рулье (1852), Г. Е. Щуровского (1856), Ф. Б. Шмидта (1867), П. А. Кропоткина (1876), английского учёного Дж. Гейки (1879) и шведского учёного О. Торелля (1875), труды которых способствовали быстрому и всеобщему признанию Л. т.

Л. т. касается главным образом последнего этапа истории Земли, для большей части которого - Плейстоцена обширные оледенения особенно характерны. Труды основателей Л. т. опирались на идеи моногляциализма, но в 20 в. подавляющее большинство исследователей перешло на позиции полигляциализма - учения о множественности оледенений. Согласно этому учению, в течение плейстоцена несколько раз чередовались холодные (ледниковья, гляциалы) и тёплые (межледниковья, интергляциалы) отрезки времени, благодаря чему покровы материковых льдов в средних широтах то возникали, то полностью стаивали. Укреплению полигляциализма особенно способствовала работа А. Пенка и Э. Брикнера по истории оледенения Альп (1909). В России и СССР внедрение полигляциалистических представлений связано с именами С. Н. Никитина, А. П. Павлова, Г. Ф. Мирчинка, С. А. Яковлева, И. П. Герасимова, К. К. Маркова, А. И. Москвитина и др. Согласно современным представлениям, неоднократные колебания климата считаются научным фактом, и споры идут главным образом о степени их резкости, числе и времени проявления.

Установлено неоднократное повторение эпох сильного похолодания климата и развития обширных материковых оледенений не только в последнем периоде геологической истории Земли, но и в гораздо более отдалённом геологическом прошлом (см. Ледниковый период). Таким образом, Л. т. приобрела общегеологическое значение, превратившись из частной концепции в составную часть общей теории изменений климата в геологическом прошлом Земли.

Лит.: Кропоткин П. А., Исследования о ледниковом периоде, в. 1-2, СПБ, 1876; Марков К. К., Ледниковая теория (Исторический очерк), в его кн.: Очерки по географии четвертичного периода, М., 1955; Марков К. К., Лазуков Г. И., Николаев В. А., Четвертичный период (Ледниковый период - антропогеновый период), т. 1-3, М., 1965-67; Флинт Р. Ф., Ледники и палеогеография плейстоцена, пер. с англ., М., 1963.

Е. В. Шанцер.

катастрофизм учение 1-й половины 19 в., рассматривавшее геологическую историю Земли как чередование длительных эпох относительного покоя и сравнительно коротких катастрофических событий, резко преображавших лик планеты. Идея о катастрофах зародившаяся в глубокой древности, в 17-18 вв. стала использоваться для истолкования геологической истории. Но т.к. длительность существования Земли до начала 19 в. оценивалась не более чем в 100 тыс. лет, было трудно объяснить действием обычных причин зафиксированные в толщах пород огромные изменения, претерпевавшиеся Землёй и её органическим миром в прошлом. Стремясь найти выход из этого затруднения, французский естествоиспытатель Ж. Кювье в 1812 выдвинул гипотезу о катастрофах (переворотах), во время которых на большей части планеты якобы погибало всё живое, а затем опустошённые места заселялись другими видами организмов, пережившими катастрофу в отдалённых районах. Это была попытка не только объяснить грандиозность прошлых преобразований Земли, но и преодолеть противоречие между господствовавшими убеждениями в неизменности видов и уже тогда прочно установленным фактом многократной смены в геологическом разрезе отличных друг от друга ископаемых флор и фаун. Идеи Кювье развивали французский палеонтолог А. д'Орбиньи, швейцарский геолог Л. Агассис, английский геолог А. Седжвик и др., насчитывавшие в геологической истории Земли 27 катастроф, во время которых якобы погибал весь органический мир. После каждой катастрофы, по представлениям этих учёных, в результате очередного божественного "акта творения" создавались совершенно новые растения и животные, не связанные с ранее существовавшими; каждый раз они были более сложно и совершенно организованы, чем предшествующие. В периоды между катастрофами никакого развития и изменений вновь созданные живые существа якобы не претерпевали. Концепция катастрофизма и неоднократных творческих актов согласовывалась с библейской версией творения мира. Принимая эту концепцию, можно было объяснить современное состояние поверхности Земли как результат последнего во времени творческого акта.

Тем не менее катастрофизм первой половины 19 в. сыграл положительную роль в развитии биостратиграфии (См. Биостратиграфия), поскольку учением о резких границах между различными по возрасту толщами и качественным своеобразием органического мира каждого периода (эпохи, века) он способствовал укреплению понятия о руководящих окаменелостях. Положительным было и то, что благодаря К. т. широко распространились идеи о прогрессе в органическом мире и об эпизодических событиях, нарушающих однообразие в истории Земли. Это способствовало формированию в дальнейшем представлений о сочетании эволюционного и скачкообразного развития. В середине 19 в. К. т. стала утрачивать своё значение в геологии благодаря победе представлений о том, что ныне действующих геологических факторов достаточно для осуществления за длительный срок всех перемен, зафиксированных в разрезе (Ч. Лайель). Позднее катастрофизм был побежден и в биологии в результате развития эволюционных представлений (Ч. Дарвином и др.). Однако отказ от идей катастрофизма не был окончательным: в 1-й половине 20 в. они частично возродились в форме так называемого неокатастрофизма - представления об одновременных на всей планете фазах складчатости и горообразования, прерывающих длительные эпохи относительного покоя и медленной эволюции коры (нем. геолог Х. Штилле и его последователи); высказываются мысли о катастрофических событиях во Вселенной, вызывающих усиленную радиацию, обусловливающую гибель одних групп организмов и быстрые мутационные изменения других, приводящие к возникновению новых видов и родов живых организмов (нем. палеонтолог О. Шиндевольф). Убедительная критика идей неокатастрофизма в тектонике дана Н. С. Шатским, а в палеонтологии - Л. Ш. Давиташвили.

В. В. Тихомиров.

раздел математики, изучающий кажущееся случайным или очень сложное поведение детерминированных динамических систем. Динамическая система - это такая система, состояние которой меняется во времени в соответствии с фиксированными математическими правилами; последние обычно задаются уравнениями, связывающими будущее состояние системы с текущим. Такая система детерминирована, если эти правила не включают явным образом элемента случайности.

Вплоть до 1960-х годов многим казалось естественным полагать, что динамическая система, описываемая простыми детерминистическими уравнениями, должна вести себя относительно просто, хотя уже более столетия было известно, что это верно лишь в некоторых весьма специальных случаях, таких, как Солнечная система. Однако к 1980 математики и естествоиспытатели обнаружили, что хаос вездесущ.

Пример хаотического поведения из повседневной жизни - движение жидкости в миксере. Это устройство подчиняется простым механическим законам: его нож-смеситель вращается с постоянной скоростью, и взаимодействие жидкости с ножом внутри миксера можно описать простыми детерминистическими уравнениями. Однако возникающее при этом движение жидкости весьма сложно. Ее соседние области рассекаются ножом и разделяются, а отдаленные области могут сближаться. Короче говоря, жидкость перемешивается - для этого миксеры и предназначены.

Выражение "теория хаоса" используется преимущественно в популярной литературе. Специалисты же рассматривают эту дисциплину как раздел теории динамических систем.

Основные принципы. Для изучения хаоса используют общие математические принципы и компьютерное моделирование. Фундаментальной характеристикой всякой динамической системы является итерация, т.е. результат повторного (многократного) применения одного и того же математического правила к некоторому выбранному состоянию. Состояние обычно описывается числом или набором чисел, но это может быть также геометрическая фигура или конфигурация. Например, пусть правилом будет "разделить на два". Начав с исходного состояния, задаваемого числом 1, это правило дает итерации 1/2, 1/4, 1/8,..., образующие очевидную закономерную последовательность. Правило "возвести в квадрат и вычесть единицу", примененное к 0, дает последовательность -1, 0, -1, 0,..., которая циклически и неограниченно скачет между числами 0 и ?1. Однако правило "возвести в квадрат, удвоить и затем вычесть единицу", если начать применять его, скажем, к значению 0,1, порождает последовательность чисел ?0,98, 0,92, 0,69, ?0,03,..., в которой не удается заметить никакой очевидной закономерности.

Основным понятием теории хаоса является аттрактор, т.е. то поведение, к которому в конце концов приходит или в пределе стремится система. Аттракторами для трех описанных выше систем являются: единственное число 0; пара чисел (0, ?1); весь интервал чисел между -1 и 1. Динамика в этих трех случаях соответственно стационарная, периодическая и хаотическая. Хаотический аттрактор обладает скрытой структурой, которая часто становится явной после графического представления итераций. Состояние динамической системы - это набор чисел, которые можно интерпретировать как координаты изображающей его точки в некотором фазовом пространстве. Когда состояние системы меняется, эта точка движется. Для стационарного аттрактора движущаяся точка стремится к фиксированному положению, а для периодического аттрактора она циклически проходит через фиксированную последовательность положений. В случае хаотического аттрактора движущаяся точка образует более сложную конфигурацию с очень хитроумной, многослойной структурой. Такие конфигурации называют фракталами; этот термин был введен в 1970 Б.Мандельбротом. Его работы впоследствии стимулировали огромное количество исследований по фрактальной геометрии.

Важной чертой хаотической динамики является ее непредсказуемость. Представим себе две частички порошка, находящиеся рядом друг с другом в жидкости внутри миксера. После включения миксера эти две частички недолго останутся рядом; они быстро разойдутся в разные стороны и вскоре начнут двигаться независимо. Подобным же образом, если дважды запустить хаотическую систему из очень близких начальных состояний, ее поведение в этих двух случаях быстро станет совершенно непохожим. Это означает, что на больших временных интервалах хаотические системы непредсказуемы. Малейшая погрешность измерения начального состояния быстро растет, и предсказание будущего состояния становится все более неточным. Однако, в отличие от случайной системы, краткосрочное прогнозирование здесь возможно.

История вопроса. Понятие хаоса не было в явном виде сформулировано до 1960-х годов, но его истоки можно проследить начиная с последнего десятилетия 19 в., когда появилась удостоенная премии работа французского математика А.Пуанкаре о движении в Солнечной системе. Двумя столетиями раньше Ньютон установил закон всемирного тяготения, из которого вывел, что движение двух притягивающихся тел в отсутствие других сил описывается просто: каждое из них перемещается относительно их общего центра масс по одному из конических сечений - окружности, эллипсу, параболе, гиперболе или прямой. Для трех или большего числа тел, однако, нельзя найти подобного простого решения, и Пуанкаре показал, что эта трудность вызвана не недостатком человеческой изобретательности, а свойствами, внутренне присущими динамике многих тел. Он установил, что даже в ограниченной задаче трех тел, масса одного из которых пренебрежимо мала, возможно столь сложное движение, что его нельзя описать никакой математической формулой. См. также НЕБЕСНАЯ МЕХАНИКА
.

В 1926-1927 голландский инженер Б.Ван-дер-Пол сконструировал электронную схему, соответствующую математической модели сердечных сокращений. Он обнаружил, что при определенных условиях возникающие в схеме колебания были не периодическими, как при нормальном сердцебиении, а нерегулярными. Его работа получила серьезное математическое обоснование в годы Второй мировой войны, когда Дж.Литтлвуд и М.Картрайт исследовали принципы радиолокации. В начале 1960-х годов американский математик С.Смейл попытался построить исчерпывающую классификацию типичных разновидностей поведения динамических систем. Поначалу он предполагал, что можно обойтись различными комбинациями периодических движений, но вскоре понял, что возможно значительно более сложное поведение. В частности, он подробнее исследовал открытое Пуанкаре сложное движение в ограниченной задаче трех тел, упростив геометрию и получив при этом систему, известную ныне как "подкова Смейла". Он доказал, что такая система, несмотря на ее детерминированность, проявляет некоторые черты случайного поведения. Другие примеры подобных явлений были разработаны американской и российской школами в теории динамических систем, причем особенно важным оказался вклад В.И.Арнольда. Так начала возникать общая теория хаоса. Сам термин "хаос" ввели Дж.Йорке и Т.Ли в 1975 в краткой статье, посвященной обсуждению некоторых результатов исследований российской школы.

Исследования хаотических систем время от времени появлялись и в литературе по прикладным вопросам. Наиболее известная из таких моделей была введена метеорологом Э.Лоренцем в 1963. Лоренц построил модель конвекции в атмосфере, создав приближения очень сложных уравнений, описывающих это явление, значительно более простыми уравнениями с тремя неизвестными. Численно решая их на компьютере, он обнаружил, что решения колеблются нерегулярным, почти случайным образом. Лоренц также установил, что если слегка изменять начальные значения переменных, то отклонения будут усиливаться, пока новое решение не окажется совершенно непохожим на исходное. Описание им этого явления в последующих лекциях привело к популярному ныне выражению "эффект бабочки": взмах крыла бабочки может изменить погоду.

Примеры приложений. Теория хаоса находит приложения в широком спектре наук. Одним из самых ранних стало ее применение к анализу турбулентности в жидкости. Движение жидкости бывает либо ламинарным (гладким и регулярным), либо турбулентным (сложным и нерегулярным). До появления теории хаоса существовали две конкурирующие теории турбулентности. Первая из них представляла турбулентность как накопление все новых и новых периодических движений; вторая объясняла неприменимость стандартной физической модели невозможностью описания жидкости как сплошной среды в молекулярных масштабах. В 1970 математики Д.Рюэль и Ф.Такенс предложили третью версию: турбулентность - это хаос в жидкости. Их предположение поначалу считалось весьма спорным, но с тех пор оно было подтверждено для нескольких случаев, в частности, для ранних стадий развития турбулентности в течении между двумя вращающимися цилиндрами. Развитая турбулентность по-прежнему остается загадочным явлением, но хаоса вряд ли удается избежать в любом возможном ее объяснении. См. также ГИДРОАЭРОМЕХАНИКА
.

Ранняя работа Э.Лоренца в области метеорологии получила дальнейшее развитие, и теперь известно, что полные уравнения поведения атмосферы, используемые при прогнозировании погоды, могут вести себя хаотически. Это означает, что долгосрочные прогнозы погоды на основе данных о ее прошлом состоянии подвержены "эффекту бабочки", так что погода обычно не может быть предсказана более чем на четыре или пять дней вперед - независимо от мощности используемых компьютеров.

Движение в Солнечной системе тоже, как известно, хаотично, но здесь требуются десятки миллионов лет, прежде чем какое-то изменение станет непредсказуемым. Хаос проявляет себя многообразными способами. Например, спутник Сатурна Гиперион обращается по регулярной, предсказуемой орбите вокруг своей планеты, но при этом он хаотически кувыркается, изменяя направление оси собственного вращения. Теория хаоса объясняет это кувыркание как побочное действие приливных сил, создаваемых Сатурном. Теория хаоса объясняет также распределение тел в поясе астероидов между Марсом и Юпитером. Оно неравномерно: на одних расстояниях от Солнца существуют сгущения, на других - пустые промежутки. И сгущения, и пустые промежутки их гелиоцентрических орбит находятся на расстояниях, образующих "резонансы" с Юпитером, т.е. период обращения каждого астероида составляет некую простую дробь с периодом обращения Юпитера. Например, в резонансе 2:3 период обращения астероида равен 2/3 периода обращения Юпитера. Теория хаоса показывает, что одни резонансы порождают устойчивое поведение (сгущения), тогда как другие - неустойчивое (пустые промежутки). В частности, астероиды в резонансе 1:3 с Юпитером имеют неустойчивые орбиты и могут испытать возмущения, заставляющие их пересечь орбиту Марса, после чего они могут испытать дальнейшие возмущения и пересечь орбиту Земли. В 1995 Ж.Ласкар установил, что на временных масштабах десятков миллионов лет вся Солнечная система хаотична. Однако хаос не делает все черты движения в Солнечной системе непредсказуемыми. Например, форма планетной орбиты может быть предсказуемой, однако точное положение планеты на орбите остается непредсказуемым. Ласкар предсказал вероятное будущее Солнечной системы в целом на следующие несколько миллиардов лет. Согласно его вычислениям, ничего существенного не случится с орбитами внешних планет - Юпитера, Сатурна, Урана, Нептуна и Плутона. Орбиты Земли и Венеры тоже не претерпели бы существенных изменений, если бы не Марс, орбита которого изменится настолько, что он едва не столкнется с Землей. Меркурий тоже приблизится к Венере и будет либо выброшен из Солнечной системы, либо поменяется местами с Венерой.

Хаос имеет место также в биологии и экологии. В конце 19 в. было установлено, что популяции животных редко бывают стабильными; им свойственны нерегулярно чередующиеся периоды быстрого роста и почти полного вымирания. Теория хаоса показывает, что простые законы изменения численности популяций могут объяснить эти флуктуации без введения случайных внешних воздействий. Теория хаоса также объясняет динамику эпидемий, т.е. флуктуирующих популяций микроорганизмов в организмах людей.

Может создаться впечатление, что теория хаоса не должна иметь каких-либо полезных применений, поскольку хаотические системы непредсказуемы. Однако это неверно, во-первых, потому, что лишь некоторые аспекты хаотических систем непредсказуемы, и, во-вторых, потому, что полезность теории не ограничивается способностью прямого прогнозирования. В частности, теория хаоса предлагает новые методы анализа данных и обнаружения скрытых закономерностей там, где прежде систему считали случайной и никаких закономерностей в ее поведении не искали, полагая, что их просто не существует. Одним из приложений этого подхода служит машина FRACMAT, обеспечивающая дешевую и быструю процедуру контроля качества пружинной проволоки.

К числу наиболее перспективных применений теории хаоса принадлежит "хаотическое управление". В 1950 Дж.фон Нейман предположил, что неустойчивость погоды может в один прекрасный день обернуться благом, поскольку неустойчивость означает, что желаемый эффект может быть достигнут очень малым возмущением. В 1990 С.Гребоджи, Э.Отт и Дж.Йорке опубликовали теоретическую схему использования этого вида неустойчивости для управления хаотическими системами. Их схема представляет собой общую форму того метода, с помощью которого в 1985 инженеры НАСА послали космический зонд на встречу с кометой Джакобини - Циннера. Зонд пять раз облетел Луну, используя хаотичность взаимодействия трех тел, позволяющую совершать большие изменения траектории с малыми затратами топлива. Тот же метод был применен для синхронизации батареи лазеров; для управления нерегулярностями сердцебиения, что открывает возможность создать "интеллектуальный" стимулятор сердечного ритма; для управления биотоками мозга, что, в частности, может помочь контролировать эпилептические припадки; наконец, для ламинаризации турбулентного течения жидкости - метод, который способен уменьшить расход топлива самолетами.

раздел математики, изучающий общие свойства Алгоритмов. Содержательные явления, приведшие к образованию понятия "алгоритм", прослеживаются в математике в течение всего времени её существования. Однако само это понятие сформировалось лишь в 20 в. и стало предметом самостоятельного изучения (по-видимому, впервые, хотя ещё в расплывчатом виде) лишь в 20-х гг. 20 в. в трудах представителей математического интуиционизма (См. Математический интуиционизм) Л. Э. Я. Брауэра и Г. Вейля (См. Вейль). Началом систематической разработки А. т. можно считать 1936, когда А. Чёрч опубликовал первое уточнение понятия вычислимой функции (См. Вычислимая функция)(предложив отождествлять понятие всюду определённой вычислимой функции, имеющей натуральные аргументы и значения, с понятием общерекурсивной функции) и привёл первый пример функции, не являющейся вычислимой, а А. М. Тьюринг и Э. Л. Пост дали первые уточнения понятия алгоритма (в терминах идеализированных вычислительных машин, см. Тьюринга машина). В дальнейшем А. т. получила развитие в трудах С. К. Клини, Э. Л. Поста, А. А. Маркова и других. В частности, А. А. Марков предложил уточнять понятие алгоритма с помощью введённого им понятия нормального алгоритма (См. Нормальный алгорифм). Наиболее общий подход к уточнению понятия алгоритма предложил А. Н. Колмогоров.

Основные понятия А. т. Областью применимости алгоритма называется совокупность тех объектов, к которым он применим. Про алгоритм ℑ говорят, что он: 1) "вычисляет функцию f", коль скоро его область применимости совпадает с областью определения f и ℑ перерабатывает всякий x из своей области применимости в f(x), 2) "разрешает множество А относительно множества X", коль скоро он применим ко всякому х из Х и перерабатывает всякий х из Х ∩ A в слово "да", а всякий х из ХA в слово "нет"; 3) "перечисляет множество В", коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В. Функция называется вычислимой, если существует вычисляющий её алгоритм. Множество называется разрешимым относительно X, если существует разрешающий его относительно Х алгоритм (см. Разрешимое множество). Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм (см. Перечислимое множество).

Детальный анализ понятия "алгоритм" обнаруживает, что (I) область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества. В свою очередь (II) для любой пары вложенных одно в другое перечислимых множеств можно подобрать алгоритм, у которого большее множество служит множеством исходных данных, а меньшее - областью применимости. Имеют место следующие основные теоремы: (III) функция f вычислима тогда и только тогда, когда перечислим её график, т. е. множество всех пар вида . (IV) Подмножество А перечислимого множества Х тогда и только тогда разрешимо относительно X, когда А и Х А перечислимы. (V) Если А и В перечислимы, то A' ∪B и А ∩В также перечислимы. (VI) В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением [в силу (IV) это перечислимое подмножество будет неразрешимым относительно X]. (VII) Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определённая на подмножестве этого множества и не продолжаемая до вычислимой функции, определённой на всём X. Утверждения (VI) и (II) в совокупности дают упоминаемый в ст. Алгоритм пример алгоритма ℑ с неразрешимой областью применимости.

Алгоритмические проблемы. Проблема построения алгоритма, обладающего теми или иными свойствами, называется алгоритмической проблемой (а. п.). Как правило, свойство искомого алгоритма формулируется в терминах свойств того соответствия, которое должно иметь место между исходными данными и результатами алгоритма. Важные примеры а. п.: проблема вычисления данной функции (требуется построить алгоритм, вычисляющий эту функцию): проблема разрешения данного множества (требуется построить алгоритм, разрешающий это множество относительно некоторого другого множества); проблема перечисления данного множества (требуется построить алгоритм, перечисляющий данное множество). Неразрешимость а. п. означает отсутствие соответствующего алгоритма; теоремы, устанавливающие неразрешимость таких проблем, относятся к числу наиболее важных теорем А. т.

Метрическая А. т. А. т. можно разделить на дескриптивную (качественную) и метрическую (количественную). Первая исследует алгоритмы с точки зрения устанавливаемого ими соответствия между исходными данными и результатами, к ней относятся, в частности, те алгоритмические проблемы, о которых говорилось в предыдущем разделе. Вторая исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и задаваемых ими "вычислений", т. е. процессов последовательного преобразования конструктивных объектов. Важно подчеркнуть, что сложность алгоритмов и вычислений может определяться различными способами, причём может оказаться, что при одном способе А будет сложнее В, а при другом способе - наоборот. Чтобы говорить о сложности алгоритмов, надо сперва описать какой-либо точный язык для записи алгоритмов и затем под сложностью алгоритма понимать сложность его записи; сложность же записи можно определять различными способами (например, как число символов данного типа, участвующих в записи, или как набор таких чисел, вычисленных для разных типов символов). Чтобы говорить о сложности вычисления, надо уточнить, как именно вычисление представляется в виде цепочки сменяющих друг друга конструктивных объектов и что считается сложностью такой цепочки (только ли число членов в ней - "число шагов" вычисления или ещё учитывается "размер" этих членов и т. п.); в любом случае сложность вычисления зависит от исходного данного, с которого начинается вычисление, поэтому сложность вычисления есть функция, сопоставляющая с каждым объектом из области применимости алгоритма сложность соответствующей цепочки. Разработка методов оценки сложности алгоритмов и вычислений имеет важное теоретическое и практическое значение, однако в отличие от дескриптивной А. т., оформившейся в целостную математическую дисциплину, метрическая А. т. делает лишь первые шаги.

Приложения А. т. имеются во всех областях математики, в которых встречаются алгоритмические проблемы. Такие проблемы возникают в математической логике и теории моделей; для каждой теории формулируется проблема разрешения множества всех истинных или доказуемых предложений этой теории относительно множества всех её предложений (теории подразделяются на разрешимые и неразрешимые - в зависимости от разрешимости или неразрешимости указанной проблемы); в 1936 А. Чёрч установил неразрешимость проблемы разрешения для множества всех истинных предложений логики предикатов, дальнейшие важные результаты в этом направлении принадлежат А. Тарскому (См. Тарский), А. И. Мальцеву и др. Алгоритмические проблемы встречаются в алгебре (проблема тождества для полугрупп и, в частности, для групп: первые примеры полугрупп с неразрешимой проблемой тождества были найдены в 1947 независимо А. А. Марковым и Э. Л. Постом, а пример группы с неразрешимой проблемой тождества - в 1952 П. С. Новиковым); в топологии (проблема гомеоморфии, неразрешимость которой для важного класса случаев была доказана в 1958 А. А. Марковым); в теории чисел (остающаяся до сих пор открытой проблема разрешимости диофантовых уравнений) и др. разделах математики.

А. т. тесно связана с математической логикой, поскольку на понятие алгоритма опирается одно из центральных понятий математической логики - понятие исчисления (См. Исчисление) и потому, например, теорема К. Гёделя (См. Гёдель) о неполноте формальных систем может быть получена как следствие теорем А. т. Наконец, А. т. тесно связана с основаниями математики, в которых одно из центральных мест занимает проблема соотношения конструктивного и неконструктивного, в частности А. т. даёт аппарат, необходимый для разработки конструктивного направления (См. Конструктивное направление) в математике; в 1965 А. Н. Колмогоров предложил использовать А. т. для обоснования информации теории (См. Информации теория). А. т. образует теоретический фундамент для ряда вопросов вычислительной математики и тесно связана с кибернетикой, в которой важное место занимает изучение алгоритмов управления, в частности понятие алгоритма занимает центральное место в т. н. программированном обучении.

Лит.: Общие вопросы. Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; Марков А. А., Теория алгорифмов, М. - Л., 1954 (Тр. Матем. института АН СССР, т. 42).

Отдельные вопросы. Колмогоров А. Н., Три подхода к определению понятия "количество информации", "Проблемы передачи информации", 1965, т. 1, в. 1; Ершов Ю. Л. [и др.], Элементарные теории, "Успехи математических наук", 1965, т. 20, в. 4; Марков А. А., О нормальных алгорифмах, связанных с вычислением булевых функций, "Известия АН СССР. Серия математическая", 1967, т. 31, в. 1; Трахтенброт Б. А., Сложность алгоритмов и вычислений, Новосиб., 1967.

В. А. Успенский.

математическая дисциплина, исследующая процессы хранения, преобразования и передачи информации (См. Информация). И. т. - существенная часть кибернетики (См. Кибернетика). В основе И. т. лежит определённый способ измерения количества информации, содержащейся в каких-либо данных ("сообщениях"). И. т. исходит из представления о том, что сообщения, предназначенные для сохранения в запоминающем устройстве (См. Запоминающее устройство) или для передачи по каналу связи, не известны заранее с полной определённостью. Заранее известно лишь множество, из которого могут быть выбраны эти сообщения, и в лучшем случае - то, как часто выбирается то или иное из этих сообщений (т. е. вероятность сообщений). В И. т. показывается, что "неопределённость", с которой сталкиваются в подобной обстановке, допускает количественное выражение и что именно это выражение (а не конкретная природа самих сообщений) определяет возможность их хранения и передачи. В качестве такой "меры неопределённости" в И. т. принимается число двоичных знаков, необходимое для фиксирования (записи) произвольного сообщения данного источника. Более точно - рассматриваются все возможные способы обозначения сообщений цепочками символов 0 и 1 (двоичные коды), удовлетворяющие условиям: а) различным сообщениям соответствуют различные цепочки и б) по записи некоторой последовательности сообщений в кодированной форме эта последовательность должна однозначно восстанавливаться. Тогда в качестве меры неопределённости принимают среднее значение длины кодовой цепочки, соответствующее самому экономному способу кодирования (См. Кодирование); один двоичный знак служит единицей измерения (см. Двоичные единицы).

Пример. Пусть некоторые сообщения x₁, x₂, x₃ появляются с вероятностями, равными соответственно ¹/₂, ³/₈, ¹/₈. Какой-либо слишком короткий код, скажем

x₁ = 0, x₂ = 1, x₃ = 01,

непригоден, так как нарушается вышеупомянутое условие б). Так, цепочка 01 может означать x₁, x₂ или x₃. Код

x₁ = 0, x₂ = 10, x₃ = 11,

удовлетворяет условиям а) и б). Ему соответствует среднее значение длины кодовой цепочки, равное

Нетрудно понять, что никакой другой код не может дать меньшего значения, т. е. указанный код - самый экономный. В соответствии с выбором меры неопределенности, неопределенность данного источника сообщении следует принять равной 1,5 двоичной единицы.

Здесь уместно подчеркнуть, что термины "сообщение", "канал связи" и т. п. понимают в И. т. очень широко. Так, с точки зрения И. т., источник сообщений описывается перечислением множества x₁, x₂,... возможных сообщений (которые могут быть словами какого-либо языка, результатами измерений, телевизионными изображениями и т. п.) и соответствующих им вероятностей p₁, p₂,...

Нет никакой простой формулы, выражающей точный минимум H' среднего числа двоичных знаков, необходимого для кодирования сообщении x₁, x₂,..., x_n через вероятности p₁, p₂,..., p_n этих сообщений. Однако указанный минимум не меньше величины

(где log₂a обозначает логарифм числа a при основании 2) и может превосходить её не более чем на единицу. Величина Н (энтропия множества сообщений) обладает простыми формальными свойствами, а для всех выходов И. т., которые носят асимптотический характер, соответствуя случаю H' → ∞, разница между H и H' абсолютно несущественна. Поэтому именно энтропия принимается в качестве меры неопределённости сообщений данного источника. В приведённом выше примере энтропия равна

С изложенной точки зрения, энтропия бесконечной совокупности оказывается, как правило, бесконечной. Поэтому в применении к бесконечным совокупностям поступают иначе. Именно, задаются определённым уровнем точности и вводят понятие ε - энтропии, как энтропии сообщения, записываемого с точностью до ε, если сообщение представляет собой непрерывную величину или функцию (например, времени); подробнее см. в ст. Энтропия.

Так же как и понятие энтропии, понятие количества информации, содержащейся в одном случайном объекте (случайной величине, случайном векторе, случайной функции и т. д.) относительно другого, вводится сначала для объектов с конечным числом возможных значений. Затем общий случай изучается при помощи предельного перехода. В отличие от энтропии, количество информации, например, в одной непрерывно распределённой случайной величине относительно другой непрерывно распределённой величины очень часто оказывается конечным.

Понятие канала связи (см. Канал) в И. т. носит весьма общий характер. По сути дела, канал связи задаётся указанием множества "допустимых сообщений" на "входе канала", множеством "сообщений на выходе" и набором условных вероятностей получения того или иного сообщения на выходе при данном входном сообщении. Эти условные вероятности описывают влияние "помех", искажающих передаваемые сообщения, "Присоединяя" к каналу какой-либо источник сообщений, можно рассчитать количество информации относительно сообщения на входе, содержащееся в сообщении на выходе. Верхняя грань таких количеств информации, взятая по всем допустимым источникам, называется пропускной способностью (ёмкостью) канала. Ёмкость канала - его основная информационная характеристика несмотря на влияние (возможно сильное) помех в канале, при определённом соотношении между энтропией поступающих сообщений и пропускной способностью канала возможна почти безошибочная передача (при надлежащем кодировании, см. Шеннона теорема).

И. т. отыскивает оптимальные, в смысле скорости и надежности, способы передачи информации, устанавливая теоретические пределы достижимого качества. Как видно из предыдущего, И. т. носит существенно статистический характер, и поэтому значительная часть ее математических методов заимствуется из теории вероятностей.

Основы И. т. были заложены в 1948-49 американским ученым К. Шенноном. В ее теоретические разделы внесен вклад советским учеными А. Н. Колмогоровым и А. Я. Хинчиным, а в разделы, соприкасающиеся с применениями, - В. А. Котельниковым, А. А. Харкевичем и др.

Лит.: Яглом А. М., Яглом И. М., Вероятность и информация, 2 изд., М., 1960; Шэннон К., Статистическая теория передачи электрических сигналов, в кн.: Теория передачи электрических сигналов при наличии помех. Сб. переводов, М., 1953; Голдман С., Теория информации, пер. с англ., М., 1957; Теория информации и её приложения. Сб. переводов, М., 1959; Хинчин А. Я., Понятие энтропии в теории вероятностей, "Успехи математических наук", 1953, т. 8, в. 3; Колмогоров А. Н., Теория передачи информации, М., 1956, (АН СССР. Сессия по научным проблемам автоматизации производства. Пленарное заседание); Питерсон У. У., Коды, исправляющие ошибки, пер. с англ., М., 1964.

Ю. В. Прохоров.